package tree.structure.question;

import tree.structure.TreeNode;
import tree.structure.TreeUtil;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @user 26233
 * @create 2020-03-21 22:17:09
 * @description
 **/

public class PathSumCompute {

    static List<Integer> path = new ArrayList<>();
    static List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args){
        //Integer[] t = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        Integer[] t = new Integer[]{1, 2, 3};
        TreeUtil<Integer> tu = new TreeUtil<>(t);
        TreeNode<Integer> root = tu.createTree(Integer.MAX_VALUE, 0);


        // new PathSumCompute().getSumPath(root, 8);
        new PathSumCompute().getSumPath2(root, root, 8);

        System.out.println("a");

    }

    public void getSumPath(TreeNode<Integer> root, int sum) {
        if(root == null)return;
        path.add(root.getValue());
        if(root.left == null && root.right == null){
            result.add(new ArrayList<>(path));
        }else{
            getSumPath(root.left, sum);
            getSumPath(root.right, sum);
        }
        path.remove(path.size() - 1);
    }

    static Stack s = new Stack();
    public void getSumPath2(TreeNode<Integer> root, TreeNode<Integer> originRoot, int sum) {
        if (root == null) return;
        if (originRoot.right == root){
            while(s.peek() != originRoot.getValue()){
                s.pop();
            }
        }
        s.push(root.getValue());
        if (root.left == null && root.right == null){
            System.out.println("s: " + s);
            s.pop();
        }else{
            getSumPath2(root.left, root, sum);
            getSumPath2(root.right, root, sum);
        }
    }
}
